package com.dayuanit.dy15.lesson23.demo2;

/**
 * 自定义双向链表  链表是不支持随机访问的  但是数组是支持随机访问
 */
public class MyLinkedList {

    private Node first;
    private Node last;

    private int size;

    public void remove(int index) {
        //被删除节点的对象
        Node node = getNode(index);

        Object item = node.item;
        //被删除节点的后一个节点对象
        Node next = node.next;
        //被删除节点的前一个节点对象
        Node pre = node.pre;

        node.pre = null;
        node.next = null;
        node.item = null;

        if (pre == null) {
            this.first = next;
        } else {
            pre.next = next;
        }

        if (next == null) {
            this.last = pre;
        } else {
            next.pre = pre;
        }

        size --;
    }

    public void add(Object item) {
        addLast(item);
    }

    public void addLast(Object item) {
        Node oldLast = this.last;
        Node newNode = new Node(oldLast, item, null);
        this.last = newNode;

        //特例：当第一添加的时候，头尾节点都是当前这个新增的节点对象
        if (oldLast == null) {
            this.first = newNode;
        } else {
            oldLast.next = newNode;
        }

        size ++;
    }

    public void addFirst(Object item) {
        Node oldFirst = this.first;
        Node newNode = new Node(null, item, oldFirst);
        first = newNode;

        //特例：当第一添加的时候，头尾节点都是当前这个新增的节点对象
        if (oldFirst == null) {
            last = newNode;
        } else {
            oldFirst.pre = newNode;
        }
        size ++;
    }

    /**
     * 查找
     * @param index
     * @return
     */
    public Object get(int index) {
        return getNode(index).item;
    }

    private Node getNode(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("越界啦， 老弟~");
        }

        if (index < (size >> 1)) {
            //从前向后查
            Node node = this.first;
            for (int i=0; i<index; i++) {
                node = node.next;
            }
            return node;
        } else {
            //从后向前查
            Node node = this.last;
            for (int i = size - 1; i>index; i--) {
                node = node.pre;
            }
            return node;
        }
    }

    public int size() {
        return this.size;
    }

}
